package com.lxl.insert;

import java.util.Arrays;

/**
 * @Classname InsertSort
 * @Description 直接插入排序
 * 是一种稳定排序
 * @Date 2021/8/12 16:13
 * @Created by LXLDEMO
 */
public class InsertSort {
    public static void main(String[] args) {
        // 测试用例
        int arr[] = {2,4,3,1,6,5};
        insertSort(arr,arr.length);
    }

    /**
     * 直接插入排序
     * @param arr
     * @param len arr.length
     */
    public static void insertSort(int[] arr,int len){
        System.out.println("初始数据 "+ Arrays.toString(arr));
        // i用作下标；i从1开始，因为一个元素就是有序的 不需要再排
        for(int i=1;i<len;i++){
            System.out.println("\n第"+i+"轮");
            int temp = arr[i]; // 防止数据丢失 为下面后移元素做准备
            System.out.println("哨兵："+temp);
            // 倒着比较，每次加入一个元素和左侧已经排序好的序列作比较
            // 左侧元素比temp大的时候 为temp腾位置 j接着左移
            int j;
            for (j=i;j>0 && arr[j-1]>temp; j--){
                arr[j] = arr[j-1];
                System.out.println("第"+i+"_"+(i-j+1)+"次交换：" + Arrays.toString(arr));
            }
            //跳出循环的时候 要么j==0 要么arr[j-1]<=temp
            //j ==0 表示temp为最小值； arr[j-1]<=temp 表示temp介于排好的最大最小之间
            arr[j] = temp;
            System.out.println("第"+i+"轮交换结果：" + Arrays.toString(arr));
        }
    }


}
